package com.yubest;

import java.util.Stack;

/**
 * 你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
 *
 * 示例 1:
 *
 * 输入: [4, 1, 8, 7]
 * 输出: True
 * 解释: (8-4) * (7-1) = 24
 * 示例 2:
 *
 * 输入: [1, 2, 1, 2]
 * 输出: False
 * 注意:
 *
 * 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
 * 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
 * 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/24-game
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/10/18 11:14
 */
public class P0679 {

    public static void main(String[] args) {
        System.out.println(new Solution679().judgePoint24(new int[]{4, 1, 8, 7}));

        System.out.println(new Solution679().judgePoint24(new int[]{1, 2, 1, 2}));
    }
}

class Solution679 {

    public boolean judgePoint24(int[] cards) {
        String[] op = {"+", "-", "*", "/"};
        //获取所有排列组合
        String r = null;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (j == i) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    for (int l = 0; l < 4; l++) {
                        if (l == i || l == j || l == k) {
                            continue;
                        }
                        for (int oi = 0; oi < 4; oi++) {
                            for (int oj = 0; oj < 4; oj++) {
                                for (int ok = 0; ok < 4; ok++) {
                                    r = cal(new Integer[] {cards[i], cards[j], cards[k], cards[l]}, new String[] {op[oi], op[oj], op[ok]});
                                    if (null != r) {
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return false;
    }

    private String cal(Integer[] num, String[] op) {
        String[] s = new String[] {String.valueOf(num[0]), op[0], String.valueOf(num[1]), op[1], String.valueOf(num[2]), op[2], String.valueOf(num[3])};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {"(", String.valueOf(num[0]), op[0], String.valueOf(num[1]), ")", op[1], String.valueOf(num[2]), op[2], String.valueOf(num[3])};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {"(", String.valueOf(num[0]), op[0], String.valueOf(num[1]), op[1], String.valueOf(num[2]), ")", op[2], String.valueOf(num[3])};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {String.valueOf(num[0]), op[0], "(", String.valueOf(num[1]), op[1], String.valueOf(num[2]), ")", op[2], String.valueOf(num[3])};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {String.valueOf(num[0]), op[0], "(", String.valueOf(num[1]), op[1], String.valueOf(num[2]), op[2], String.valueOf(num[3]), ")"};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {String.valueOf(num[0]), op[0], String.valueOf(num[1]), op[1], "(", String.valueOf(num[2]), op[2], String.valueOf(num[3]), ")"};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {"(", String.valueOf(num[0]), op[0], String.valueOf(num[1]), ")", op[1], "(", String.valueOf(num[2]), op[2], String.valueOf(num[3]), ")"};
        if (calculator(s)) {
            return String.join("", s);
        }
        s = new String[] {"(", String.valueOf(num[0]), op[0], String.valueOf(num[1]), ")", op[1], "(", String.valueOf(num[2]), op[2], String.valueOf(num[3]), ")"};
        if (calculator(s)) {
            return String.join("", s);
        }
        return null;
    }

    private boolean calculator(String[] unit) {
        Stack<int[]> ints = new Stack<>();
        Stack<String> op = new Stack<>();
        int[] c;
        String cUnit;
        for (String anUnit : unit) {
            //如果是符号
            if ("+-*/()".contains(anUnit)) {
                cUnit = anUnit;
                while (!op.isEmpty()) {
                    if (null == cUnit) {
                        if ("(".contains(op.peek())) {
                            break;
                        }
                        int[] b = ints.pop();
                        int[] a = ints.pop();
                        c = cal(a, b, op.pop());
                        ints.push(c);
                    } else if ("+-".contains(cUnit)) {
                        if ("(".contains(op.peek())) {
                            break;
                        }
                        int[] b = ints.pop();
                        int[] a = ints.pop();
                        c = cal(a, b, op.pop());
                        ints.push(c);
                        cUnit = null;
                    } else if ("*/".contains(cUnit)) {
                        if ("(+-".contains(op.peek())) {
                            break;
                        }
                        int[] b = ints.pop();
                        int[] a = ints.pop();
                        c = cal(a, b, op.pop());
                        ints.push(c);
                        cUnit = null;
                    } else if ("(".contains(cUnit)) {
                        break;
                    } else if (")".contains(cUnit)) {
                        int[] b = ints.pop();
                        int[] a = ints.pop();
                        c = cal(a, b, op.pop());
                        ints.push(c);
                        if ("(".contains(op.peek())) {
                            op.pop();
                            cUnit = null;
                        }
                    }
                }
                if (!")".contains(anUnit)) {
                    op.push(anUnit);
                }
            }
            //如果是数字
            else {
                ints.push(new int[]{Integer.valueOf(anUnit), 1});
            }
        }
        while (!op.isEmpty()) {
            int[] b = ints.pop();
            int[] a = ints.pop();
            c = cal(a, b, op.pop());
            ints.push(c);
        }
        int[] r = ints.pop();
        int m = Math.min(r[0], r[1]);
        for (int i = 2; i <= m; i++) {
            if (r[0] % i == 0 && r[1] % i == 0) {
                r[0] = r[0] / i;
                r[1] = r[1] / i;
                i = 2;
            }
        }
        return r[1] != 0 && (r[0] % r[1] == 0) && (r[0] / r[1] == 24);
    }

    private static int[] cal(int[] a, int[] b, String op) {
        int[] r = new int[2];
        if ("+".equals(op)) {
            r[0] = a[0] * b[1] + b[0] * a[1];
            r[1] = a[1] * b[1];
        } else if ("-".equals(op)) {
            r[0] = a[0] * b[1] - b[0] * a[1];
            r[1] = a[1] * b[1];
        } else if ("*".equals(op)) {
            r[0] = a[0] * b[0];
            r[1] = a[1] * b[1];
        } else {
            r[0] = a[0] * b[1];
            r[1] = a[1] * b[0];
        }
        return r;
    }
}
